﻿#define _CRT_SECURE_NO_WARNINGS 1

//Day16-01 牛客：字符串模拟，题号：2590852
//解法:模拟
//string formatString(string A, int n, vector<char> arg, int m)
//{
//    string ret;
//    int pos = 0;
//    for (int i = 0; i < n;)
//    {
//        if (i + 1 < n && A[i] == '%' && A[i + 1] == 's')
//        {
//            ret += arg[pos++];
//            i += 2;
//        }
//        else
//        {
//            ret += A[i++];
//        }
//    }
//    while (pos < m)
//    {
//        ret += arg[pos++];
//    }
//    return ret;
//}


//Day16-02 牛客：神奇数，题号：100343
//解法:模拟+数学
//bool IsPrim(int x)
//{
//	if (x < 2) return false;
//	for (int i = 2; i <= sqrt(x); i++)
//	{
//		if (x % i == 0) return false;
//	}
//	return true;
//}
//
//bool check(int x)
//{
//	string s = to_string(x);
//	for (int i = 0; i < s.size(); i++)
//	{
//		for (int j = i + 1; j < s.size(); j++)
//		{
//			string tmp1, tmp2;
//			tmp1 = tmp1 + s[i] + s[j];
//			tmp2 = tmp2 + s[j] + s[i];
//			if ((tmp1[0] != '0' && IsPrim(stoi(tmp1))) || (tmp2[0] != '0' && IsPrim(stoi(tmp2))))
//				return true;
//		}
//	}
//	return false;
//}
//
//int main()
//{
//	int a, b;
//	cin >> a >> b;
//	int ret = 0;
//	//神奇数是一个两位数，小于10的数没必要枚举
//	for (int i = max(a, 10); i <= b; i++)
//	{
//		if (check(i)) ret++;
//	}
//	cout << ret;
//}


//Day16-03 牛客：DNA序列，题号：10055182
//解法:滑动窗口
//string s;
//int x;
//int main()
//{
//    cin >> s >> x;
//    int begin = -1;
//    int count = 0; // 统计窗口内'C'和'G'的个数
//    int maxCount = 0; //统计之前窗口内'C'和'G'的个数的最大值
//    int n = s.size();
//    for (int left = 0, right = 0; right < n; right++)
//    {
//        if (s[right] == 'C' || s[right] == 'G') count++;
//        while (right - left + 1 > x)
//        {
//            if (s[left] == 'C' || s[left] == 'G') count--;
//            left++;
//        }
//        if (right - left + 1 == x)
//        {
//            if (count > maxCount)
//            {
//                begin = left;
//                maxCount = count;
//            }
//        }
//    }
//    cout << s.substr(begin, x);
//    return 0;
//}


//Day17-01 牛客：小乐乐改数字，题号：632017
//解法:模拟
//int main()
//{
//    string s;
//    cin >> s;
//    for (auto& i : s)
//    {
//        if (i % 2 == 0) i = '0';
//        else i = '1';
//    }
//    cout << stoi(s) << endl;
//    return 0;
//}


//Day17-02 牛客：十字爆破，题号：955384
//解法:预处理+模拟
//typedef long long LL;
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    vector<vector<LL>> arr(n, vector<LL>(m));
//    vector<LL> row(n), col(m);//预处理
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            scanf("%lld", &arr[i][j]);
//            row[i] += arr[i][j];
//            col[j] += arr[i][j];
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            cout << row[i] + col[j] - arr[i][j] << " ";
//        }
//        cout << endl;
//    }
//
//    return 0;
//}


//Day17-03 牛客：⽐那名居的桃⼦，题号：1928660
//解法1:前缀和
//const int N = 1e5 + 10;
//int n, k;
//LL a[N], b[N], happy[N], shame[N];
////前缀和
//int main()
//{
//    cin >> n >> k;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i];
//        happy[i] = happy[i - 1] + a[i];
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> b[i];
//        shame[i] = shame[i - 1] + b[i];
//    }
//    LL h = 0, s = 0;
//    int pos = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        LL tmp1 = happy[i + k - 1 <= n ? i + k - 1 : n] - happy[i - 1];
//        LL tmp2 = shame[i + k - 1 <= n ? i + k - 1 : n] - shame[i - 1];
//        if (tmp1 > h || (tmp1 == h && tmp2 < s))
//        {
//            h = tmp1;
//            s = tmp2;
//            pos = i;
//        }
//    }
//    cout << pos;
//    return 0;
//}

//解法2:滑动窗口
//typedef long long LL;
//const int N = 1e5 + 10;
//int n, k;
//LL h[N], s[N];
//LL hSum, sSum;
//LL hMax, sMin;
//
//int main()
//{
//    cin >> n >> k;
//    LL ret = 0;
//    for (int i = 1; i <= n; i++) cin >> h[i];
//    for (int i = 1; i <= n; i++) cin >> s[i];
//    for (int left = 1, right = 1; right <= n; right++)
//    {
//        hSum += h[right], sSum += s[right];
//        while (right - left + 1 > k)
//        {
//            hSum -= h[left], sSum -= s[left];
//            left++;
//        }
//        if (right - left + 1 == k)
//        {
//            if (hSum > hMax || (hSum == hMax && sSum < sMin))
//            {
//                ret = left;
//                hMax = hSum;
//                sMin = sSum;
//            }
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}